//
//  WordBreak.swift
//  LeetCodeDemo
//
//  Created by OS on 2022/7/15.
//

import Foundation

/*
 139. 单词拆分
 */

class WordBreak {
    
    /*
     动态规划
     
     */
    
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        let n = s.count
        var dp = [Bool](repeating: false, count: n + 1)
        dp[0] = true
        let hash = Set<String>(wordDict)
        for i in 1..<n + 1 {
            for j in 0..<i {
                let startIndex = s.index(s.startIndex, offsetBy: j)
                let endIndex = s.index(s.startIndex, offsetBy: i)
                let substring = String(s[startIndex..<endIndex])
                if dp[j] && hash.contains(substring) {
                    dp[i] = true
                }
            }
        }
        return dp[n]
    }
}
